package leetcode_jz_offer.day19_huisuAndBinTree;

/**
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先
 * 最近公共祖先的定义为：“对于有根树T的两个结点p、q,最近公共祖先表示为一个结点x
 * 满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）。”
 **/

/**
 * 用整型变量接收是否找到节点p,q
 * 我们在找p或q的祖先时顺便找最近公共祖先
 */
public class Num68_I二叉树的最近公共祖先 {
    private class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    //定义一个全局变量用于返回最近公共祖先
    private TreeNode resNode;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      lowestCommonAncestorHelper(root,p,q);
      return resNode;
    }

  /**
   * 以当前root为根节点的二叉树是否能找到p或q
   * 该方法不是找公共祖先的方法，只是判断当前树是否是p或q的祖先，找到一个就说明至少是一个结点的祖先
   * 只是找是否是p或q的祖先的过程中判断了是否是公共祖先
   */
  private Boolean lowestCommonAncestorHelper(TreeNode root, TreeNode p, TreeNode q) {
    if(root==null){
      return false;
    }
    //判断左右子树是否有包含p或q，根节点是否是p或q
    int left=lowestCommonAncestorHelper(root.left,p,q)?1:0;
    int right=lowestCommonAncestorHelper(root.right,p,q)?1:0;
    int mid=(root==p||root==q)?1:0;
    if(left+right+mid==2){
      resNode=root;//相加和为2，根节点就是最近公共祖先
    }
    //否则，有没有祖先就是看就是看上面有没有大于零的数
    return left+right+mid>0;
  }
}
